package lcr;

import java.util.ArrayList;
import java.util.List;

public class Test0086 {
}

class Solution0086_1 {
    char[] chars;
    ArrayList<List<String>> records=new ArrayList<>();
    public String[][] partition(String s) {
        chars=s.toCharArray();

        traceback(0,new ArrayList<>());
        int size = records.size();
        String[][] ans = new String[size][];
        for (int i = 0; i < size; i++) {
            List<String> now = records.get(i);
            ans[i]= now.toArray(new String[0]);
        }

        return ans;
    }

    public void traceback(int index,List<String> list){
        int length = chars.length;
        if (length==index) records.add(new ArrayList<>(list));

        for (int i = index; i < length; i++) {
            if (!isHuiWen(index,i)) continue;

            list.add(String.valueOf(chars, index, i-index+1));
            traceback(i+1,list);
            list.remove(list.size()-1);
        }
    }

    public boolean isHuiWen(int l,int r){
        while (l<r)
            if (chars[l++]!=chars[r--]) return false;

        return true;
    }
}
